﻿using System;
using System.IO;
using System.Text;

public sealed class StreamSearcher
{
    public const int MAX_PATTERN_LENGTH = 1024;
    private readonly int[] _borders;
    private readonly byte[] _pattern;

    public StreamSearcher(byte[] pattern)
    {
        _pattern = new byte[pattern.Length];
        Array.Copy(pattern, _pattern, pattern.Length);
        _borders = new int[_pattern.Length + 1];
        preProcess();
    }


    private void preProcess()
    {
        var i = 0;
        var j = -1;
        _borders[i] = j;

        while (i < _pattern.Length)
        {
            while (j >= 0 && _pattern[i] != _pattern[j])
            {
                j = _borders[j];
            }
            _borders[++i] = ++j;
        }
    }


    public long Search(Stream stream) //KMP搜索算法
    {
        long bytesRead = 0;

        int b;
        var j = 0;

        while ((b = stream.ReadByte()) != -1)
        {
            bytesRead++;

            while (j >= 0 && (byte)b != _pattern[j])
            {
                j = _borders[j];
            }

            ++j;

            if (j == _pattern.Length)
            {
                return bytesRead;
            }
        }

        return -1;
    }
}

class Searching
{
    static readonly int buffer_size = 1024;
    public static void SearchingProcess(string filePath, byte[] patternBytes)
    {
        var searcher = new StreamSearcher(patternBytes); //创建搜索器
        foreach (var fname in new[] { filePath })
        {
            using (var stream = File.Open(fname, FileMode.Open, FileAccess.ReadWrite))
            {
                using (var sr = new BinaryReader(stream))
                {
                    while (sr.BaseStream.Position + patternBytes.Length < sr.BaseStream.Length) //是否读到最后一帧
                    {
                        try
                        {
                            byte[] data = sr.ReadBytes(buffer_size); //读一帧
                            var ms = new MemoryStream(data); //创建内存流
                            while (ms.Position < ms.Length) //没有读到内存流末尾
                            {
                                var position = searcher.Search(ms); //搜索在内存流中匹配的位置
                                if (position == -1) //找不到匹配位置，不再搜索
                                {
                                    stream.Seek(stream.Position - (patternBytes.Length - 1), SeekOrigin.Begin);  //回退到前一帧不超过模式串长度位置                                       
                                    break;
                                }
                                else //找到
                                {
                                    var patternPosition = stream.Position - (ms.Length - ms.Position) - patternBytes.Length; //确定该帧在原文件流对应绝对位置
                                    Console.WriteLine($"关键词位置：{patternPosition}"); //这里只做了简单输出，可以做原始流截取帧处理
                                    patternPosition++; //下一帧的开始位置

                                }
                            }
                        }
                        catch (EndOfStreamException ex)

                        {
                            Console.WriteLine("Done!");
                            break;
                        }
                    }
                }

            }
        }
    }
}




class Program
{
    static void Main()
    {
        var patternBytes = new byte[] { 0x01, 0x02, 0x03, 0x04 };
        string filePath = "C:\\Users\\leomojys\\Downloads\\input.bin";
        Searching.SearchingProcess(filePath, patternBytes);
    }
}